from typing import List


class Solution:
    def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:
        # 最优做法是合并连续 k+1 个空余时间段

        # 求会议间的空余时间段数组rest
        rest = []
        if startTime[0] != 0:
            rest.append(startTime[0])
        for idx in range(1, len(startTime)):
            rest.append(startTime[idx] - endTime[idx - 1])
        if endTime[len(endTime) - 1] < eventTime:
            rest.append(eventTime - endTime[len(endTime) - 1])

        # k大于rest数组长，直接返回rest元素和
        window_size = k + 1
        if len(rest) <= window_size:
            return sum(rest)

        # 普通场景，等价于定长滑动窗口
        end = window_size
        ret = 0
        cur = sum(rest[end - window_size: end])
        while end <= len(rest):
            # 性能优化，片段和通过加减法求出，避免循环中调用sum
            # 性能优化2，转化为前缀和
            if end != window_size:
                cur += rest[end - 1]
                cur -= rest[end - window_size - 1]
            if cur > ret:
                ret = cur
            end += 1
        return ret
